package com.mc.sort;

public class HeapSort3 {
	
	public static void main(String[] args){
		int[] data = {4,2,5,6,1,2,6,7,8};
		int n  =data.length;
		for(int i=(n/2-1);i>=0;i--){
			sink(i,data,n);
		}
		int k = data.length-1;
		while(k>=0){
			System.out.println(data[0]);
			data[0] = data[k--];
			sink(0,data,n--);
		}
	}
	public static void sink(int i,int[] data,int n){
		while((2*i+1)<n){//左子树存在
			int j = 2*i+1;
			if((j+1)<n&&data[j]>data[j+1])j++;
			if(data[i]<=data[j])break;
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			i = j;
		}
	}
	
}
